package com.zwh.algorithm.leetcode.medium;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LeetCode43 {
    /**
     * 2023-08-01  重排链表
     * todo 给定一个单链表 L 的头节点 head ，单链表 L 表示为：
     * todo L0 → L1 → … → Ln - 1 → Ln
     * todo 请将其重新排列后变为：
     * todo L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
     * todo 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
     */
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
//        ListNode listNode5 = new ListNode(5);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
//        listNode4.next = listNode5;
        reorderList(listNode1);
        while (listNode1 != null){
            System.out.println(listNode1.val);
            listNode1 = listNode1.next;
        }
    }

    public static void reorderList(ListNode head) {
        ListNode listNode = new ListNode();
        listNode = head;
        List<ListNode> list = new ArrayList<>();
        while (listNode != null){
            list.add(listNode);
            listNode = listNode.next;
        }
        int len =list.size();
        if (len < 3){
            return;
        }
        int l = len / 2;
        listNode = head;
        for (int i = 1; i < len /2; i++) {
            head.next = list.get(len -i);
            head = head.next;
            head.next = list.get(i);
            head = head.next;
        }
        if (len % 2 == 0){
            head.next = list.get(len/2);
        }else{
            head.next = list.get(len/2 +1);
            head = head.next;
            head.next = list.get(len/2);
        }
        head = head.next;
        head.next = null;
        head = listNode;
    }

    public static void reorderList1(ListNode head) {
        if (head == null) {
            return;
        }
        List<ListNode> list = new ArrayList<ListNode>();
        ListNode node = head;
        while (node != null) {
            list.add(node);
            node = node.next;
        }
        int i = 0, j = list.size() - 1;
        while (i < j) {
            list.get(i).next = list.get(j);
            i++;
            if (i == j) {
                break;
            }
            list.get(j).next = list.get(i);
            j--;
        }
        list.get(i).next = null;
    }

    static class ListNode {
     int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}
